package 开始的剑指offer8月.搜索与回溯算法;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

// https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
public class 剑指Offer34二叉树中和为某一值的路径0827 {

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        Deque<Integer> path = new LinkedList<Integer>();

        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root, target);
            return ret;
        }

        public void dfs(TreeNode root, int target) {
            if (root == null) {
                return;
            }
            path.offerLast(root.val);
            target -= root.val;
            if (root.left == null && root.right == null && target == 0) {
                ret.add(new LinkedList<Integer>(path));
            }
            dfs(root.left, target);
            dfs(root.right, target);
            path.pollLast();
        }
    }

}
